数据结构四叉树 quadTree

包含的用例代码 simplequadtree 里面内含了一个绘图工具，方便打印四叉树

四叉树是什么？

二叉树的变体二叉查找树，非常适合用来进行对一维数列的存储和查找，可以达到 $O(logn)$ 的效率；我们在用二叉查找树进行插入数据时，根据一个数据的值和树结点值的对比，选择二叉树的两个叉之一向下，直到叶子结点，查找时使用二分法也可以迅速找到需要的数据。

但二叉树只支持一维数据，如一个标量数值，对地图上的位置点这种有xy两个方向上的信息却无能为力，那么是否有一种树能够支持二维数据的快速查询呢？

所以这时可以使用四叉树来完成两个轴向的查找（同理三维可以使用八叉树）

四叉树是种很直接的空间索引技术。在四叉树中，每个节点表示覆盖了部分进行索引的空间的边界框，根节点覆盖了整个区域。每个节点要么是叶节点，有包含一个或多个索引点的列表，没有孩子。要么是内部节点，有四个孩子，每个孩子对应将区域沿两根轴对半分得到的四个象限中的一个，四叉树也因此得名。

它为每个结点添加一个“容量”的属性，在四叉树初始化时只有一个根结点，在插入数据时，如果一个结点内的数据量大于了结点“容量”，再将结点进行分裂。如此，可以保证每个结点内都存储着数据，避免了内存空间的浪费。

在查询时，只有找到了位置对应的结点，那么结点下的所有点都会是此位置的附近点，更小的“容量”意味着每个结点内点越少，也就意味着查询的精度会越高。

四叉树位置点的插入流程如下图所示：

注意：只有叶子节点里面才会存在元素

定义结构

const MAX_ELE_NUM = 100

// Region 表示节点保存元素的范围
type Region struct {
    up     int
    bottom int
    left   int
    right  int
}

// ElePoint 保存真实的数据
type ElePoint struct {
    x    int
    y    int
    data string
}

// QuadTreeNode 一个四叉树节点，里面包含若干个元素
type QuadTreeNode struct {
    depth   int                    // 节点深度
    isLeaf  bool                   // 是否是叶子节点
    region  Region                 // 区域范围
    LU      *QuadTreeNode          // 左上子结点指针
    LB      *QuadTreeNode          // 左下子结点指针
    RU      *QuadTreeNode          // 右上子结点指针
    RB      *QuadTreeNode          // 右下子结点指针
    eleNum  int                    // 位置点数
    eleList [MAX_ELE_NUM]*ElePoint // 位置点列表
}

如上，一个 Node 内部包含多个元素，该 Node 表示一个范围，当该 Node 下的节点大于最大元素数量则进行裂变操作

四叉树的操作

节点分裂

当满足特定条件时，为了获得更好的检索效率，四叉树的节点会发生分裂，分裂的做法是：以当前节点的矩形为中心，划分出四个等大的矩形，作为四个子节点，每个节点深度=当前节点深度+1，根节点深度为0；并且将当前节点的元素重新插入到对应的子节点。

/**
 * 分裂结点
 * 1.通过父结点获取子结点的深度和范围
 * 2.生成四个结点，挂载到父结点下
 *
 * @param node
 */
func splitNode(node *QuadTreeNode) {
    midVertical := (node.region.up + node.region.bottom) / 2
    midHorizontal := (node.region.left + node.region.right) / 2
    node.isLeaf = false

    node.RU = newChildNode(node, midVertical, node.region.up, midHorizontal, node.region.right)
    node.LU = newChildNode(node, midVertical, node.region.up, node.region.left, midHorizontal)
    node.RB = newChildNode(node, node.region.bottom, midVertical, midHorizontal, node.region.right)
    node.LB = newChildNode(node, node.region.bottom, midVertical, node.region.left, midHorizontal)

    // 遍历结点下的位置点，将其插入到子结点中
    for i := 0; i < node.eleNum; i++ {
        InsertEle(node, *node.eleList[i])
        node.eleList[i] = nil // 释放空间
        node.eleNum--
    }
}

插入元素

平面的元素多种多样，点，线，图形，但都能够做一个统一，第一步都是要找出图形所覆盖的节点，这里以矩形为例

从根节点开始，如果当前节点无子节点，将元素插入到当前节点。如果存在子节点K，并且元素能够完全被子节K点所“包围”，就将元素插入到子节点K，对于子节点K进行上述递归操作；如果元素跨越了多个子节点，那就将元素存储在当前节点

如果某一节点元素超过特定值，并且深度小于四叉树允许的最大深度，分裂当前节点。

/**
 * 插入元素
 * 1.判断是否已分裂，已分裂的选择适合的子结点，插入；
 * 2.未分裂的查看是否过载，过载的分裂结点，重新插入；
 * 3.未过载的直接添加
 *
 * @param node
 * @param ele
 */
func InsertEle(node *QuadTreeNode, ele ElePoint) {
    if node.isLeaf {
        // 如果该节点包含的元素已经大于最大的元素数量则分裂节点
        if node.eleNum+1 > MAX_ELE_NUM {
            splitNode(node)
            InsertEle(node, ele)
        } else {
            elePtr := &ElePoint{}
            elePtr.y = ele.y
            elePtr.x = ele.x
            elePtr.data = ele.data
            node.eleList[node.eleNum] = elePtr
            node.eleNum++
        }
        return
    }

    midVertical := (node.region.up + node.region.bottom) / 2
    midHorizontal := (node.region.left + node.region.right) / 2

    // 把元素插入到对应的节点
    if ele.y > midVertical {
        if ele.x > midHorizontal {
            InsertEle(node.RU, ele)
        } else {
            InsertEle(node.LU, ele)
        }
    } else {
        if ele.x > midHorizontal {
            InsertEle(node.RB, ele)
        } else {
            InsertEle(node.LB, ele)
        }
    }
}

检索

对于给定检索区域，从根节点起，如果检索区域与当前节点有交集，返回当前节点的所有元素。

如果当前节点还有子节点，递归检索与检索区域有交集的子节点。

// 找到元素的所在的 Node
func QueryNodeByElement(node *QuadTreeNode, ele *ElePoint) {
    fmt.Printf("%+v %+v %+v %+v \n\n", node.depth, node.region, node.isLeaf, node.eleNum)
    if node.isLeaf {
        fmt.Printf("当前 Node 附近点有 %d 个，分别是：\n", node.eleNum)
        for i := 0; i < node.eleNum; i++ {
            // fmt.Printf("(%f,%f) \n", node.eleList[i].x, node.eleList[i].y)
        }
        return
    }

    midVertical := (node.region.up + node.region.bottom) / 2
    midHorizontal := (node.region.left + node.region.right) / 2

    if ele.y > midVertical {
        if ele.x > midHorizontal {
            QueryNodeByElement(node.RU, ele)
        } else {
            QueryNodeByElement(node.LU, ele)
        }
    } else {
        if ele.x > midHorizontal {
            QueryNodeByElement(node.RB, ele)
        } else {
            QueryNodeByElement(node.LB, ele)
        }
    }
}

References

空间管理Space management：四叉树 & 八叉树四叉树应用于地图（点聚合）、碰撞检测等问题空间索引 - 四叉树

四叉树是什么？​

定义结构​

四叉树的操作​

节点分裂​

插入元素​

检索​

References​